package com.unionfind;

/**
 * @Author: tgy
 * @Date: 2020-10-20 09:42
 */
public class UnionFind_QF extends AbstractUnionFind {

    public UnionFind_QF(int capacity) {
        super(capacity);
    }

    @Override
    protected int find(int v) {

        checkV(v);
        return parents[v];
    }

    @Override
    protected void union(int v1, int v2) {

        int parentV1 = find(v1);
        int parentV2 = find(v2);

        if (parentV1 == parentV2) {
            return;
        }

        /**
         * 把所有与 v1同parent节点的parent改成v2的parent
         */
        for (int i = 0; i < parents.length; i++) {

            if (parents[i] == parentV1) {
                parents[i] = parentV2;
            }
        }
    }
}
